package org.example.struct.array;

/**
 * @author liyishan
 * @date 2023/8/23 09:42
 * @apiNote
 */

public class Test01539FindKthPositive {
    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 7, 11};
        int count = test1(arr, 5);
        System.out.println(count);
    }

    public static int test(int[] arr, int k) {
        int missCount = 0, lastMiss = -1, current = 1, ptr = 0;
        for (missCount = 0; missCount < k; ++current) {
            if (current == arr[ptr]) {
                ptr = (ptr + 1 < arr.length) ? ptr + 1 : ptr;
            } else {
                ++missCount;
                lastMiss = current;
            }
        }
        return lastMiss;
    }


    public static int test1(int[] arr, int k) {
        if (arr[0] > k) {
            return k;
        }
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            int x= arr[mid];
            if (x - mid - 1 >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return k - (arr[l - 1] - (l - 1) - 1) + arr[l - 1];
    }
}
